package leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-23 15:55
 **/
public class LeetCode150 {

    //匹配数字的正则表达式
    private static final String REGEX_NUMBER = "\\d+";

    /*public int evalRPN(String[] tokens) {
        //用来存储操作数
        Deque<Integer> stack = new LinkedList<>();
        // 用来存储两个操作数
        int a = 0;
        int b = 0;
        for (String token : tokens) {
            //判断当前字符串是否是数字
            if (token.matches(REGEX_NUMBER)) {
                stack.push(Integer.valueOf(token));
            } else {
                a = stack.pop();
                b = stack.pop();
                switch (token) {
                    case "+": {
                        stack.push(a + b);
                        break;
                    }
                    case "-": {
                        stack.push(b - a);
                        break;
                    }
                    case "*": {
                        stack.push(b * a);
                        break;
                    }
                    default: {
                        stack.push(b / a);
                        break;
                    }
                }
            }
        }
        return stack.pop();
    }*/

    /**
     * 使用了数组充当栈
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        //使用数组作为栈
        int[] stack = new int[(tokens.length + 1) /2];
        //指向栈的第二元素。
        int index = -1;
        for (String token : tokens) {
            switch (token) {
                case "+": {
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                }
                case "-": {
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                }
                case "*": {
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                }
                case "/": {
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                }
                default: {
                    index++;
                    stack[index] = Integer.parseInt(token);
                }
            }
        }
        return stack[index];
    }

    public static void main(String[] args) {
        /*Pattern pattern = Pattern.compile(REGEX_NUMBER);
        Matcher matcher = pattern.matcher("2");
        boolean matches = matcher.matches();
        System.out.println(String.valueOf(matches));*/
        /*boolean matches = "1".matches(REGEX_NUMBER);
        System.out.println(String.valueOf(matches));*/

        LeetCode150 code = new LeetCode150();
        code.evalRPN(new String[]{"10","6", "9", "3","+", "-11", "*","/","*","17","+","5", "+"});
    }

}
